package code.homework;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author cc
 * @create 2023-01-29  21:26
 */
public class CountSmaller {
    public static List<Integer> countSmaller(int[] nums) {
        ArrayList<Integer> res = new ArrayList<>(nums.length);
        ArrayList<Element> elements = new ArrayList<>(nums.length);
        for(int i =0 ;i<nums.length;i++){
            res.add(0);
            elements.add(new Element(nums[i],i));
        }
        count(elements,res,0,nums.length-1);
        return res;
    }

     static void count(List<Element> nums,List<Integer> values,int left,int right){
        if(left != right){
            int mid = (left+right)/2;
            count(nums,values,left,mid);
            count(nums,values,mid+1,right);

            /**
             *  1.假设左边有序，且右边有序
             *   二分法找到左边元素 <右边的元素个数  arr_left[i] >= arr_right[j], 即为 j-mid
             */
            for (int i =left ;i<=mid;i++){
                int j = mid;
                int low = mid+1;
                int high = right;
                while(low <= high){
                    if(high == 33 && i ==22){
                        System.out.println(30);
                    }
                    if((low == high && nums.get(low).getValue() <nums.get(i).getValue())
                            || (nums.get((low+high)/2).getValue() < nums.get(i).getValue()
                                && nums.get(((low+high)/2)+1).getValue() >=nums.get(i).getValue())){
                        j = (low+high)/2;
                        break;
                    }
                    if(nums.get((low+high)/2).getValue() >= nums.get(i).getValue()){
                        high = (low+high)/2 -1;
                    }else{
                        low = (low+high)/2 + 1;
                    }
                }
                if(nums.get(i).getValue() == 13){
                    System.out.println(13);
                }
                values.set(nums.get(i).getIndex(),values.get(nums.get(i).getIndex()) + j-mid);
            }
            System.out.println("values: " + values);
            /**
             * 排序
             */
            Element[] sorted = new Element[right -left +1];
            int l = left;
            int r = mid+1;
            int sortedArrIndex = 0;
            while(l <= mid || r <= right) {
                if(l > mid) {
                    sorted[sortedArrIndex ++] = nums.get(r++);
                }else if( r > right) {
                    sorted[sortedArrIndex ++] = nums.get(l++);
                }else{
                    if(nums.get(l).getValue() < nums.get(r).getValue()){
                        sorted[sortedArrIndex++] = nums.get(l++);
                    }else {
                        sorted[sortedArrIndex++] = nums.get(r++);
                    }
                }
            }
            System.out.print("sorted list : "+Arrays.asList(sorted));
            System.out.println("");
            for(int i =0 ; i<right -left +1 ;i++){
                nums.set(i+left,sorted[i]);
            }
        }
    }

    public static void main(String[] args) {
        int[] ints = {26,78,27,100,33,67,90,23,66,5,38,7,35,23,52,22,83,51,98,69,81,32,78,28,94,13,2,97,3,76,99,51,9,21,84,66,65,36,100,41};
        System.out.println("result:" +countSmaller(ints).toString());
    }

     static class Element{
        int value;
        int index;
        public Element(int value,int index){
            this.value = value;
            this.index = index;
        }

        public Integer getValue(){
            return this.value;
        }

        public Integer getIndex(){
            return this.index;
        }
        @Override
        public String toString(){
            return "value: "+this.value +",index: "+this.index;
        }
    }

}
